package com.剑指2;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 *
 * @author： leon
 * @description：
 * @date： 2022/9/13
 * @version: 1.0
 */
public class Solution {


    /**
     * 001 整数除法
     *
     * @param a
     * @param b
     * @return
     */
    public static int divide(int a, int b) {
        if (a == Integer.MIN_VALUE && b == -1) {
            return Integer.MAX_VALUE;
        }
        if (b == 1 || b == -1) {
            return b < 0 ? -a : a;
        }
        // 将 a b 转换为 负数
        int flag = 1;
        if (a < 0) {
            flag = flag * -1;
        } else {
            a = -a;
        }
        if (b < 0) {
            flag = flag * -1;
        } else {
            b = -b;
        }

        int ans = 0;
        while (a <= b) {
            int t = 1;
            int m = b;
            // 防止越界
            while (m + m < 0 && a < m + m) {
                m += m;
                t += t;
            }
            // 二分查找 ，上界为 m+m,下界为 m;
            a -= m;
            ans += t;
        }

        return ans * flag;
    }

    /**
     * 002 二进制加法
     *
     * @param a
     * @param b
     * @return
     */
    public static String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;
        while (i >= 0 || j >= 0) {
            int m = i >= 0 ? a.charAt(i--) - '0' : 0;
            int n = j >= 0 ? b.charAt(j--) - '0' : 0;
            int sum = m + n + carry;
            carry = sum >> 1;
            sb.append(sum & 1);
        }
        if (carry > 0) {
            sb.append('1');
        }

        return sb.reverse().toString();
    }

    /**
     * 003 前 n 个数字二进制中 1 的个数
     *
     * @param n
     * @return
     */
    public static int[] countBits(int n) {
        int[] ans = new int[n + 1];

        for (int i = 0; i <= n; i++) {
            ans[i] = (i & 1) + ans[i >> 1];
        }
        return ans;

    }

    /**
     * 004 只出现一次的数字
     *
     * @param nums
     * @return
     */
    public strictfp int singleNumber(int[] nums) {
        int ans = 0;
        for (int i = 0; i < 32; ++i) {
            int total = 0;
            for (int num : nums) {
                total += ((num >> i) & 1);
            }
            if (total % 3 != 0) {
                ans |= (1 << i);
            }
        }
        return ans;
    }


    /**
     * 005 单词长度的最大乘积
     *
     * @param words
     * @return
     */
    public static int maxProduct(String[] words) {

        int ans = 0;
        int[] tmp = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            int anInt = string2Int(words[i]);
            tmp[i] = anInt;
            for (int j = i - 1; j >= 0; j--) {
                if ((tmp[i] & tmp[j]) == 0) {
                    ans = Math.max(words[i].length() * words[j].length(), ans);
                }
            }
        }
        return ans;
    }

    /**
     * 字符串转整数
     *
     * @param word
     * @return
     */
    public static int string2Int(String word) {
        int ans = 0;
        for (int i = 0; i < word.length(); i++) {
            ans |= (1 << (word.charAt(i) - 'a'));
        }
        return ans;
    }

    /**
     * 006 排序数组中两个数字之和
     *
     * @param numbers
     * @param target
     * @return
     */
    public static int[] twoSum(int[] numbers, int target) {

        int i = 0, j = numbers.length - 1;
        while (i < j) {
            int tmp = numbers[i] + numbers[j];
            if (tmp == target) {
                return new int[]{i, j};
            } else if (tmp < target) {
                i++;
            } else {
                j--;
            }
        }
        return null;
    }


    /**
     * 三数之和
     * 007. 数组中和为 0 的三个数
     *
     * @param nums
     * @return
     */
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums.length < 3) {
            System.out.println("数组长度小于3");
            return ans;
        }
        // 为什么要排序？排序是为了方便去重
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {

            if (i == 0 || nums[i] != nums[i - 1]) {
                int k = nums.length - 1;
                for (int j = i + 1; j < nums.length - 1; j++) {
                    if (j == i + 1 || nums[j] != nums[j - 1]) {
                        while (j < k && nums[i] + nums[j] + nums[k] > 0) {
                            k--;
                        }
                        if (j >= k) {
                            break;
                        }
                        if (nums[i] + nums[j] + nums[k] == 0 && (k == nums.length - 1 || nums[k] != nums[k + 1])) {
                            ArrayList<Integer> tmp = new ArrayList<>();
                            tmp.add(nums[i]);
                            tmp.add(nums[j]);
                            tmp.add(nums[k]);
                            ans.add(tmp);
                        }
                    }
                }
            }
        }
        return ans;
    }

    /**
     * 008. 和大于等于 target 的最短子数组
     *
     * @param target
     * @param nums
     * @return
     */
    public static int minSubArrayLen(int target, int[] nums) {
        int ans = nums.length + 1;
        int sum = 0;
        int left = 0, right = 0;
        while (right < nums.length) {
            sum += nums[right];
            if (sum >= target) {
                ans = Math.min(ans, right - left + 1);
            }
            while (sum >= target) {
                sum -= nums[left++];
                if (sum >= target) {
                    ans = Math.min(ans, right - left + 1);
                }
            }
            right++;
        }
        return ans > nums.length ? 0 : ans;
    }

    /**
     * 009. 乘积小于 K 的子数组
     *
     * @param nums
     * @param k
     * @return
     */
    public static int numSubarrayProductLessThanK(int[] nums, int k) {

        int ans = 0;
        int left = 0, right = 0;
        int product = 1;
        while (right < nums.length) {
            product *= nums[right];
            if (product < k) {
                ans += (right - left + 1);
            }
            while (left <= right && product >= k) {
                product /= nums[left++];
                if (product < k) {
                    ans += (right - left + 1);
                }
            }
            right++;
        }
        return ans;
    }


    /**
     * 010. 和为 k 的子数组
     *
     * @param nums
     * @param k
     * @return
     */
    public static int subarraySum(int[] nums, int k) {
        int[] prefix = new int[nums.length + 1];
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 1; i < prefix.length; i++) {
            ans += map.getOrDefault(prefix[i] - k, 0);
            map.put(prefix[i], map.getOrDefault(prefix[i], 0) + 1);
        }
        return ans;

    }

    /**
     * 011. 0 和 1 个数相同的子数组
     *
     * @param nums
     * @return
     */
    public static int findMaxLength(int[] nums) {
        // 将 0 改为 -1，转化为前缀和问题
        int[] preSums = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            preSums[i + 1] = preSums[i] + (nums[i] == 0 ? -1 : 1);
        }

        Map<Integer, List<Integer>> map = new HashMap<>();

        for (int i = 0; i < preSums.length; i++) {
            List<Integer> list = map.getOrDefault(preSums[i], new ArrayList<>());
            list.add(i);
            map.put(preSums[i], list);
        }

        int ans = 0;
        for (int i = preSums.length - 1; i >= 0; i--) {
            List<Integer> list = map.getOrDefault(preSums[i], new ArrayList<>());
            for (Integer j : list) {
                if (j != i) {
                    ans = Math.max(i - j, ans);
                    break;
                }
            }
        }
        return ans;
    }

    /**
     * 011. 0 和 1 个数相同的子数组 (优化空间和时间的方法)
     *
     * @param nums
     * @return
     */
    public static int findMaxLength1(int[] nums) {
        // 用哈希表来存储首个出现元素的位置(首个元素出现的位置，必然与后面的位置差是最大的)
        Map<Integer, Integer> map = new HashMap<>();
        // 通过count来代替前缀和数组
        int count = 0;

        // 结果
        int ans = 0;
        map.put(0, -1);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                count--;
            } else {
                count++;
            }
            if (map.containsKey(count)) {
                ans = Math.max(i - map.get(count), ans);
            } else {
                map.put(count, i);
            }
        }
        return ans;

    }

    /**
     * 012. 左右两边子数组的和相等
     *
     * @param nums
     * @return
     */
    public static int pivotIndex(int[] nums) {

        int right = 0;
        for (int i = 0; i < nums.length; i++) {
            right += nums[i];
        }
        int left = 0;
        for (int i = 0; i < nums.length; i++) {
            right -= nums[i];
            if (left == right) {
                return i;
            }
            left += nums[i];
        }
        return -1;
    }


    /**
     * 013. 二维子矩阵的和
     */
    class NumMatrix {

        private int[][] preSumMatrix;

        public NumMatrix(int[][] matrix) {
            preSumMatrix = new int[matrix.length][matrix[0].length];
            for (int i = 0; i < preSumMatrix.length; i++) {
                for (int j = 0; j < preSumMatrix[i].length; j++) {
                    int left = i > 0 ? preSumMatrix[i - 1][j] : 0;
                    int up = j > 0 ? preSumMatrix[i][j - 1] : 0;
                    int leftAndUp = i > 0 && j > 0 ? preSumMatrix[i - 1][j - 1] : 0;
                    preSumMatrix[i][j] = matrix[i][j] + left + up - leftAndUp;
                }
            }

        }

        public int sumRegion(int row1, int col1, int row2, int col2) {
            int left = col1 > 0 ? preSumMatrix[row2][col1 - 1] : 0;
            int up = row1 > 0 ? preSumMatrix[row1 - 1][col2] : 0;
            int leftAndUp = col1 > 0 && row1 > 0 ? preSumMatrix[row1 - 1][col1 - 1] : 0;
            return preSumMatrix[row2][col2] - left - up + leftAndUp;

        }
    }

    /**
     * II 014. 字符串中的变位词
     *
     * @param s1
     * @param s2
     * @return
     */
    public static boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) {
            return false;
        }
        // 用哈希表存储s1 的每个元素 以及 元素个数
        Map<Character, Integer> map = new HashMap<>();
        int wight = s1.length();
        for (int i = 0; i < s1.length(); i++) {
            map.put(s1.charAt(i), map.getOrDefault(s1.charAt(i), 0) - 1);
        }

        for (int i = 0; i < wight; i++) {
            map.put(s2.charAt(i), map.getOrDefault(s2.charAt(i), 0) + 1);
            if (map.get(s2.charAt(i)) == 0) {
                map.remove(s2.charAt(i));
            }
        }
        if (map.isEmpty()) {
            return true;
        }
        for (int i = wight; i < s2.length(); i++) {
            map.put(s2.charAt(i - wight), map.getOrDefault(s2.charAt(i - wight), 0) - 1);
            map.put(s2.charAt(i), map.getOrDefault(s2.charAt(i), 0) + 1);
            if (map.containsKey(s2.charAt(i - wight)) && map.get(s2.charAt(i - wight)) == 0) {
                map.remove(s2.charAt(i - wight));
            }
            if (map.containsKey(s2.charAt(i)) && map.get(s2.charAt(i)) == 0) {
                map.remove(s2.charAt(i));
            }
            if (map.isEmpty()) {
                return true;
            }
        }
        return false;
    }

    /**
     * 014. 字符串中的变位词 ,优化版本 固定一个大小为s1.length()的窗口
     * @param s1
     * @param s2
     * @return
     */
    public static boolean checkInclusion1(String s1, String s2) {
        if (s1.length() > s2.length()) {
            return false;
        }
        int[] map = new int[26];
        int diff = 0;
        int wight = s1.length() - 1;
        for (int i = 0; i < s1.length(); i++) {
            if (map[s1.charAt(i)-'a']==0){
                diff++;
            }
            map[s1.charAt(i) - 'a']--;

        }
        for (int i = 0; i < s2.length(); i++) {

            if (map[s2.charAt(i) - 'a'] == 0) {
                diff++;
            }
            map[s2.charAt(i) - 'a']++;
            if (map[s2.charAt(i) - 'a'] == 0) {
                diff--;
            }

            if (i >= wight) {
                if (diff == 0)
                    return true;
                if (map[s2.charAt(i - wight) - 'a'] == 0) {
                    diff++;
                }
                map[s2.charAt(i - wight) - 'a']--;
                if (map[s2.charAt(i - wight) - 'a'] == 0) {
                    diff--;
                }
            }


        }
        return false;

    }

    /**
     *  015. 字符串中的所有变位词
     * @param s
     * @param p
     * @return
     */
    public static List<Integer> findAnagrams(String p, String s) {
        int[] map = new int[26];
        int diff = 0;
        for (int i = 0; i < s.length(); i++) {
            if (map[s.charAt(i)-'a']==0){
                diff++;
            }
            map[s.charAt(i)-'a']--;
        }
        int wight = s.length()-1;
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < p.length(); i++) {
            if (map[p.charAt(i)-'a']==0){
                diff++;
            }
            map[p.charAt(i)-'a']++;
            if (map[p.charAt(i)-'a']==0){
                diff--;
            }

            if (i>=wight){
                if (diff==0){
                    ans.add(i-wight);
                }

                if (map[p.charAt(i-wight)-'a']==0){
                    diff++;
                }
                map[p.charAt(i-wight)-'a']--;
                if (map[p.charAt(i-wight)-'a']==0){
                    diff--;
                }

            }
        }
        return ans;

    }


    /**
     *  016. 不含重复字符的最长子字符串
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int left = 0,right=0;
        int ans = 0;
        while (right<s.length()){

            while (set.contains(s.charAt(right))){
                set.remove(s.charAt(left++));
            }
            set.add(s.charAt(right++));
            ans = Math.max(ans,right-left);
        }
        return ans;

    }

    /**
     * 017. 含有所有字符的最短字符串
     * @param s
     * @param t
     * @return
     */
    public static String minWindow(String s, String t) {
        // 代表起始位置和终止位置
        int[] ans = new int[2];
        // 代表子串长度
        int subLen = s.length()+1;

        Map<Character,Integer> map = new HashMap<>();
        int diff = 0;
        for (int i = 0; i < t.length(); i++) {
            if (map.containsKey(t.charAt(i))){
                map.put(t.charAt(i),map.get(t.charAt(i))+1);
            }else {
                map.put(t.charAt(i),1);
                diff++;
            }
        }
        int left =0,right=0;
        while (right<s.length()){
            while (left<=right&&diff==0){
                if (right-left<subLen){
                    ans[0] = left;
                    ans[1] = right;
                    subLen = right - left;
                }
                if (map.containsKey(s.charAt(left))){
                    map.put(s.charAt(left),map.get(s.charAt(left))+1);
                    if (map.get(s.charAt(left))==1){
                        diff++;
                    }
                }

                left++;
            }
            if (map.containsKey(s.charAt(right))){
                if (map.containsKey(s.charAt(right))){
                    map.put(s.charAt(right),map.get(s.charAt(right))-1);
                    if (map.get(s.charAt(right))==0){
                        diff--;
                    }
                }
            }
            right++;
        }
        return subLen>s.length()?"":s.substring(ans[0],ans[1]+1);

    }


    public static void main(String[] args) {
        System.out.println(minWindow("ADOBECODEBANC",
                "ABC"));
    }


}
